import sys
# Install gurobi
!{sys.executable} -m pip install -i https://pypi.gurobi.com gurobipy
!{sys.executable} -m pip install plotly geopy
import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
import pandas as pd
from itertools import product
import gurobipy as gp
from gurobipy import GRB, quicksum
# These are ours
import problem
import visualization
Looking in indexes: https://pypi.gurobi.com Requirement already satisfied: gurobipy in /opt/anaconda3/lib/python3.8/site-packages (9.1.1) Requirement already satisfied: plotly in /opt/anaconda3/lib/python3.8/site-packages (4.14.3) Requirement already satisfied: geopy in /opt/anaconda3/lib/python3.8/site-packages (2.1.0) Requirement already satisfied: six in /opt/anaconda3/lib/python3.8/site-packages (from plotly) (1.15.0) Requirement already satisfied: retrying>=1.3.3 in /opt/anaconda3/lib/python3.8/site-packages (from plotly) (1.3.3) Requirement already satisfied: geographiclib<2,>=1.49 in /opt/anaconda3/lib/python3.8/site-packages (from geopy) (1.50)
def normalize(i, j):
assert i != j
return (i, j) if i < j else (j, i)
from model import Autonomax, Config
# Run on the first |C| cities (mostly for testing)
C = 41
# What scenario we will be utilizing
scenario = 0
# The number of cities in the core net
NC = 4
# 1 if the core net should be a cycle; 0 if it shoul be a path.
Z = 1
autonomax = Autonomax(
Config(
cities=problem.cities[:C],
distances=problem.D[:C, :C],
demand=problem.B[scenario][:C],
core_city_count=NC,
core_net_is_cycle=Z,
)
)
Academic license - for non-commercial use only - expires 2021-05-15 Using license file /Users/sjurwold/gurobi.lic
A = autonomax.model.getA()
count = lambda d: len(d) if isinstance(d, gp.tupledict) else 1
V = sum(count(v) for v in autonomax.variables.values())
C = sum(count(c) for c in autonomax.constraints.values())
print(f'V = {V}, C = {C}')
fig, ax = plt.subplots(1, figsize=(128, 128 * C/V))
ax.set_xticklabels([])
ax.set_yticklabels([])
plt.spy(A)
total = 0
print(f'\nCONSTRAINT SETS:')
for (name, constraint) in autonomax.constraints.items():
constraints_in_set = count(constraint)
print(f'{constraints_in_set:>5} | {name}')
#plt.gcf().text(0.07, 0.69 - 0.4 * (total + 0.5 * count(constraint)) / C, name, fontsize=14)
total += constraints_in_set
plt.plot([0, V], [total - 0.5, total - 0.5], color='grey')
total = 0
print(f'\nVARIABLE SETS:')
for (name, variables) in autonomax.variables.items():
variables_in_set = count(variables)
print(f'{variables_in_set:>5} | {name}')
#plt.gcf().text(0.1 + 0.8 * (total + 0.5*count(variables)) / V, 0.8, name, fontsize=14)
total += count(variables)
plt.plot([total - 0.5, total - 0.5], [0, C], color='grey')
plt.savefig('constraint-matrix.png', dpi=200)
V = 9389, C = 6153
CONSTRAINT SETS:
1 | one_control_center
41 | control_city_directly_connected
1681 | reduce_control_center_symmetry
41 | core_city_ub
1 | cycle_or_path
41 | disallow_core_tree
1 | exactly_nc_core_cities
41 | control_center_is_connected
2460 | is_connectable
123 | is_connected_timestep
41 | connected_graph
41 | conservation_of_flow
820 | force_edge_if_flow
820 | edge_cost_lb
VARIABLE SETS:
41 | is_control_center
820 | is_core_edge
41 | is_core_city
164 | is_connected_step
5043 | is_connectable_step
820 | flow
820 | abs_flow
820 | is_sub_edge
820 | edge_cost
autonomax.model.Params.timeLimit = 600.0
autonomax.model.optimize()
Changed value of parameter timeLimit to 600.0
Prev: inf Min: 0.0 Max: inf Default: inf
Gurobi Optimizer version 9.1.1 build v9.1.1rc0 (mac64)
Thread count: 8 physical cores, 8 logical processors, using up to 8 threads
Optimize a model with 6153 rows, 9389 columns and 30299 nonzeros
Model fingerprint: 0xc49bf554
Model has 820 general constraints
Variable types: 2460 continuous, 6929 integer (6929 binary)
Coefficient statistics:
Matrix range [1e+00, 2e+05]
Objective range [1e+00, 2e+04]
Bounds range [1e+00, 1e+02]
RHS range [7e-01, 4e+01]
Presolve removed 93 rows and 2633 columns
Presolve time: 0.09s
Presolved: 6060 rows, 6756 columns, 30309 nonzeros
Variable types: 2460 continuous, 4296 integer (4296 binary)
Found heuristic solution: objective 88012.481927
Root relaxation: objective 1.531060e+03, 5203 iterations, 0.13 seconds
Nodes | Current Node | Objective Bounds | Work
Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time
0 0 1531.06029 0 148 88012.4819 1531.06029 98.3% - 0s
H 0 0 56219.378601 1531.06029 97.3% - 0s
H 0 0 26291.282650 2035.67488 92.3% - 0s
0 0 2496.88681 0 247 26291.2827 2496.88681 90.5% - 0s
H 0 0 22932.121931 2496.88681 89.1% - 0s
0 0 3195.95627 0 213 22932.1219 3195.95627 86.1% - 0s
0 0 3195.97935 0 208 22932.1219 3195.97935 86.1% - 0s
0 0 3352.66847 0 322 22932.1219 3352.66847 85.4% - 0s
0 0 3361.96333 0 316 22932.1219 3361.96333 85.3% - 0s
0 0 3367.26315 0 351 22932.1219 3367.26315 85.3% - 0s
0 0 3368.00607 0 351 22932.1219 3368.00607 85.3% - 0s
0 0 3368.01742 0 352 22932.1219 3368.01742 85.3% - 0s
0 0 3371.24076 0 407 22932.1219 3371.24076 85.3% - 1s
0 0 3376.32460 0 349 22932.1219 3376.32460 85.3% - 1s
0 0 3376.41830 0 329 22932.1219 3376.41830 85.3% - 1s
0 0 3385.28766 0 322 22932.1219 3385.28766 85.2% - 1s
0 0 3393.25321 0 307 22932.1219 3393.25321 85.2% - 1s
0 0 3399.55904 0 328 22932.1219 3399.55904 85.2% - 1s
0 0 3399.77551 0 332 22932.1219 3399.77551 85.2% - 1s
0 0 3400.81526 0 318 22932.1219 3400.81526 85.2% - 1s
0 0 3400.86624 0 300 22932.1219 3400.86624 85.2% - 1s
0 0 3401.38822 0 371 22932.1219 3401.38822 85.2% - 1s
0 0 3401.38920 0 362 22932.1219 3401.38920 85.2% - 1s
H 0 0 20458.793698 3401.38920 83.4% - 1s
0 0 3401.86941 0 303 20458.7937 3401.86941 83.4% - 1s
0 0 3401.86941 0 265 20458.7937 3401.86941 83.4% - 2s
H 0 0 19869.314167 3401.86941 82.9% - 2s
0 2 3401.89759 0 252 19869.3142 3401.89759 82.9% - 2s
H 31 40 19211.749615 3581.29864 81.4% 523 3s
H 32 40 18446.066483 3581.29864 80.6% 511 3s
H 71 80 17486.992036 3581.29864 79.5% 349 3s
H 72 80 17394.029414 3581.29864 79.4% 346 3s
H 112 119 17260.979930 3581.29864 79.3% 284 4s
H 112 119 17215.667895 3581.29864 79.2% 284 4s
H 115 119 17026.054430 3581.29864 79.0% 281 4s
H 167 172 16966.965510 3581.29864 78.9% 226 4s
H 172 172 16953.979724 3581.29864 78.9% 224 4s
H 173 172 16934.095273 3581.29864 78.9% 222 4s
H 395 373 16895.063284 3581.29864 78.8% 137 5s
H 396 373 16840.552031 3581.29864 78.7% 137 5s
H 400 373 16779.533948 3581.29864 78.7% 137 5s
* 830 789 127 16689.915461 3743.37268 77.6% 92.3 6s
H 895 773 16064.503392 3743.85872 76.7% 91.5 6s
H 1035 905 16062.488194 3743.85872 76.7% 89.1 6s
H 1040 905 16053.351895 3743.85872 76.7% 89.1 6s
H 1044 904 15898.838430 3743.85872 76.5% 89.8 6s
1553 1323 8672.84706 19 220 15898.8384 3743.85872 76.5% 83.4 10s
H 1564 1263 15895.048881 3743.85872 76.4% 82.8 13s
1571 1268 13560.2623 136 304 15895.0489 3743.85872 76.4% 82.4 15s
1576 1275 3743.85872 15 276 15895.0489 3743.85872 76.4% 103 20s
1619 1299 7619.72284 19 407 15895.0489 4054.38721 74.5% 116 25s
1808 1354 8423.55555 28 241 15895.0489 4054.38721 74.5% 137 30s
H 1873 1314 15895.048877 4054.38721 74.5% 138 31s
H 1932 1263 15895.048851 4054.38721 74.5% 141 32s
H 1935 1205 15895.048758 4054.38721 74.5% 141 32s
H 2005 1156 15895.048689 4054.38721 74.5% 142 33s
H 2011 1102 15895.048684 4054.38721 74.5% 143 33s
2165 1127 7760.50094 44 189 15895.0487 4054.38721 74.5% 144 35s
H 2299 1052 15895.048611 4054.38721 74.5% 147 35s
H 2578 1045 15895.048560 5713.87382 64.1% 153 38s
2860 1068 cutoff 24 15895.0486 6333.75127 60.2% 157 40s
3496 1183 9327.45633 32 193 15895.0486 6876.79526 56.7% 160 45s
H 3688 1243 15895.048505 7005.60093 55.9% 161 46s
4159 1382 14892.2129 41 157 15895.0485 7610.40923 52.1% 160 50s
H 4606 1556 15895.048499 7925.13098 50.1% 162 53s
H 4637 1556 15895.048488 7925.13098 50.1% 162 53s
4839 1632 infeasible 57 15895.0485 8094.05239 49.1% 163 55s
5855 1922 cutoff 32 15895.0485 8708.47547 45.2% 162 60s
7064 2199 14712.8532 61 115 15895.0485 9618.00205 39.5% 166 65s
H 7360 2235 15895.048482 9763.59617 38.6% 167 67s
8262 2384 13405.5675 56 162 15895.0485 10278.0029 35.3% 169 71s
9314 2517 cutoff 42 15895.0485 10891.9209 31.5% 172 75s
10419 2695 15703.2113 65 99 15895.0485 11264.8002 29.1% 172 80s
11643 2805 12712.6356 39 73 15895.0485 11517.9008 27.5% 174 86s
12540 2893 14872.1679 78 85 15895.0485 11772.3504 25.9% 174 90s
14321 2969 13492.5809 59 147 15895.0485 12128.8305 23.7% 174 96s
15621 2992 13041.5460 61 168 15895.0485 12412.1406 21.9% 174 101s
17386 2881 cutoff 49 15895.0485 12674.8277 20.3% 174 106s
18660 2754 14758.4119 53 119 15895.0485 12942.8205 18.6% 174 112s
19657 2524 15447.5172 53 153 15895.0485 13164.8743 17.2% 174 117s
21185 2152 15246.0709 63 59 15895.0485 13525.3288 14.9% 174 123s
H21220 2152 15895.048460 13535.1511 14.8% 174 123s
H21396 2152 15895.048302 13559.7918 14.7% 174 123s
21432 1838 cutoff 79 15895.0483 13632.2690 14.2% 174 126s
23060 995 14932.1272 55 112 15895.0483 14070.4030 11.5% 173 131s
25118 75 cutoff 43 15895.0483 15197.6490 4.39% 169 137s
Cutting planes:
Gomory: 40
Cover: 333
Implied bound: 29
MIR: 130
Flow cover: 333
Inf proof: 11
Zero half: 22
Mod-K: 1
RLT: 420
Relax-and-lift: 24
Explored 28472 nodes (4301975 simplex iterations) in 137.58 seconds
Thread count was 8 (of 8 available processors)
Solution count 10: 15895 15895 15895 ... 16062.5
Optimal solution found (tolerance 1.00e-04)
Best objective 1.589504830216e+04, best bound 1.589504830216e+04, gap 0.0000%
city_info = pd.DataFrame(autonomax.city_info())
city_info
| Index | Name | IsCoreCity | IsControlCenter | Demand | IngoingFlow | OutgoingFlow | |
|---|---|---|---|---|---|---|---|
| 0 | 0 | Boden | False | False | 4.5 | 4.000000e+00 | 8.500000 |
| 1 | 1 | Borås | False | False | 0.7 | 1.030000e+01 | 10.999999 |
| 2 | 2 | Eskilstuna | False | False | 1.1 | 2.520000e+01 | 26.300000 |
| 3 | 3 | Falun | False | False | 2.3 | 1.207923e-13 | 2.300000 |
| 4 | 4 | Gävle | True | False | 1.0 | 1.046000e+02 | 105.600000 |
| 5 | 5 | Göteborg | False | False | 5.8 | 6.652456e-13 | 5.800000 |
| 6 | 6 | Halmstad | False | False | 3.4 | 6.100000e+00 | 9.500000 |
| 7 | 7 | Haparanda | False | False | 4.6 | 0.000000e+00 | 4.600000 |
| 8 | 8 | Helsingborg | False | False | 2.2 | 3.900000e+00 | 6.100000 |
| 9 | 9 | Hudiksvall | False | False | 3.9 | 2.740000e+01 | 31.300000 |
| 10 | 10 | Jönköping | False | False | 1.2 | 1.243450e-12 | 1.200000 |
| 11 | 11 | Kalmar | False | False | 4.0 | 1.599999e+00 | 5.599999 |
| 12 | 12 | Karlskrona | False | False | 1.6 | 4.121148e-13 | 1.600000 |
| 13 | 13 | Karlstad | False | False | 0.9 | 1.229239e-12 | 0.900000 |
| 14 | 14 | Kiruna | False | False | 4.0 | 2.398523e-08 | 4.000000 |
| 15 | 15 | Kristianstad | False | False | 3.0 | 5.400125e-13 | 3.000000 |
| 16 | 16 | Lidköping | False | False | 1.2 | 1.340000e+01 | 14.600000 |
| 17 | 17 | Linköping | False | False | 4.1 | 7.400000e+00 | 11.500000 |
| 18 | 18 | Luleå | False | False | 2.0 | 1.310000e+01 | 15.100000 |
| 19 | 19 | Malmö | False | False | 2.6 | 1.300000e+00 | 3.900000 |
| 20 | 20 | Motala | False | False | 2.4 | 1.200000e+00 | 3.600000 |
| 21 | 21 | Norrköping | False | False | 1.7 | 1.890000e+01 | 20.599999 |
| 22 | 22 | Nyköping | False | False | 4.6 | 1.357137e-12 | 4.600000 |
| 23 | 23 | Sandviken | True | False | 4.5 | 1.079000e+02 | 112.400000 |
| 24 | 24 | Skellefteå | False | False | 4.4 | 1.510000e+01 | 19.499999 |
| 25 | 25 | Skövde | False | False | 2.5 | 1.100000e+01 | 13.500000 |
| 26 | 26 | Stockholm | False | False | 7.0 | 9.521273e-13 | 7.000000 |
| 27 | 27 | Sundsvall | False | False | 0.7 | 2.670000e+01 | 27.400000 |
| 28 | 28 | Trelleborg | False | False | 1.3 | 1.350031e-12 | 1.300000 |
| 29 | 29 | Uddevalla | False | False | 4.0 | 5.800000e+00 | 9.800000 |
| 30 | 30 | Umeå | False | False | 3.2 | 1.950000e+01 | 22.700000 |
| 31 | 31 | Uppsala | True | False | 1.9 | 7.140000e+01 | 73.299999 |
| 32 | 32 | Varberg | False | False | 0.8 | 9.500000e+00 | 10.300000 |
| 33 | 33 | Vetlanda | False | False | 2.1 | 5.300000e+00 | 7.400000 |
| 34 | 34 | Vänersborg | False | False | 3.6 | 9.800000e+00 | 13.400000 |
| 35 | 35 | Västervik | False | False | 1.8 | 5.599999e+00 | 7.399999 |
| 36 | 36 | Västerås | True | True | 1.4 | 1.754000e+02 | 64.399999 |
| 37 | 37 | Växjö | False | False | 2.3 | 3.000000e+00 | 5.300000 |
| 38 | 38 | Örebro | False | False | 4.1 | 3.260000e+01 | 36.700000 |
| 39 | 39 | Örnsköldsvik | False | False | 3.1 | 2.270000e+01 | 25.800000 |
| 40 | 40 | Östersund | False | False | 0.9 | 2.048473e-08 | 0.900000 |
edge_info = pd.DataFrame(autonomax.edge_info())
edge_info
| From | To | Type | Flow | Cost | Distance | |
|---|---|---|---|---|---|---|
| 0 | Skellefteå | Umeå | SUB | 19.499999 | 731.139133 | 111 |
| 1 | Eskilstuna | Västerås | SUB | 26.299999 | 244.508409 | 43 |
| 2 | Gävle | Hudiksvall | SUB | -31.300000 | 1278.724564 | 118 |
| 3 | Skövde | Örebro | SUB | 13.500000 | 657.432752 | 132 |
| 4 | Lidköping | Örebro | SUB | 14.600000 | 841.276358 | 148 |
| 5 | Linköping | Norrköping | SUB | 11.500000 | 116.139455 | 44 |
| 6 | Motala | Örebro | SUB | 3.599999 | 110.457914 | 92 |
| 7 | Boden | Kiruna | SUB | -3.999999 | 637.912777 | 291 |
| 8 | Linköping | Vetlanda | SUB | -7.400000 | 389.358963 | 138 |
| 9 | Sundsvall | Östersund | SUB | -0.899999 | 70.870141 | 166 |
| 10 | Kalmar | Västervik | SUB | 5.599999 | 300.208529 | 139 |
| 11 | Halmstad | Helsingborg | SUB | -6.100000 | 145.447337 | 79 |
| 12 | Umeå | Örnsköldsvik | SUB | 22.700000 | 849.479945 | 111 |
| 13 | Boden | Luleå | SUB | 8.500000 | 58.656839 | 32 |
| 14 | Karlstad | Örebro | SUB | 0.900000 | 29.229970 | 77 |
| 15 | Halmstad | Varberg | SUB | 9.500000 | 167.432216 | 65 |
| 16 | Lidköping | Vänersborg | SUB | -13.400000 | 206.938975 | 60 |
| 17 | Uddevalla | Vänersborg | SUB | 9.800000 | 39.823253 | 21 |
| 18 | Gävle | Sandviken | CORE | 105.600000 | 250.000000 | 25 |
| 19 | Sandviken | Västerås | CORE | 112.400000 | 1100.000000 | 110 |
| 20 | Sundsvall | Örnsköldsvik | SUB | -25.800000 | 1177.683887 | 127 |
| 21 | Jönköping | Motala | SUB | 1.200000 | 52.590906 | 108 |
| 22 | Eskilstuna | Nyköping | SUB | -4.600000 | 119.995513 | 83 |
| 23 | Vetlanda | Växjö | SUB | -5.300000 | 112.394025 | 72 |
| 24 | Borås | Varberg | SUB | -10.300000 | 260.758783 | 84 |
| 25 | Haparanda | Luleå | SUB | 4.600000 | 210.858567 | 124 |
| 26 | Luleå | Skellefteå | SUB | 15.099999 | 742.410208 | 133 |
| 27 | Stockholm | Uppsala | SUB | 7.000000 | 136.873708 | 69 |
| 28 | Kristianstad | Växjö | SUB | 2.999999 | 134.707628 | 120 |
| 29 | Norrköping | Västervik | SUB | -7.399999 | 287.369478 | 112 |
| 30 | Falun | Sandviken | SUB | 2.299999 | 48.115159 | 65 |
| 31 | Uppsala | Västerås | CORE | -64.399999 | 780.000000 | 78 |
| 32 | Gävle | Uppsala | CORE | -73.299999 | 600.000000 | 60 |
| 33 | Kalmar | Karlskrona | SUB | -1.599999 | 45.527155 | 79 |
| 34 | Helsingborg | Malmö | SUB | -3.900000 | 67.318060 | 60 |
| 35 | Göteborg | Uddevalla | SUB | 5.800000 | 117.417503 | 70 |
| 36 | Malmö | Trelleborg | SUB | -1.299999 | 18.150073 | 34 |
| 37 | Västerås | Örebro | SUB | -36.699999 | 1050.855589 | 93 |
| 38 | Hudiksvall | Sundsvall | SUB | -27.400000 | 641.652314 | 81 |
| 39 | Eskilstuna | Norrköping | SUB | -20.599999 | 681.069442 | 102 |
| 40 | Borås | Skövde | SUB | 10.999999 | 384.262775 | 105 |
core_cost = sum(edge_info[edge_info['Type'] == 'CORE']['Cost'])
subnet_cost = sum(edge_info[edge_info['Type'] == 'SUB']['Cost'])
total_cost = core_cost + subnet_cost
print(f'core = {core_cost:>9.3f}')
print(f'subnet = {subnet_cost:>9.3f}')
print('------------------')
print(f'total = {total_cost:>9.3f}')
assert abs(autonomax.model.getObjective().getValue() - total_cost) < 1e-6
core = 2730.000 subnet = 13165.048 ------------------ total = 15895.048
visualization.show(pd.DataFrame(autonomax.city_info()), pd.DataFrame(autonomax.edge_info()))